(10 bodů) Na vstupu je dáno
vzestupně setříděné pole a celých čísel délky n, v němž se čísla mohou libovolně opakovat
a celá čísla d a h taková, že d ≤ h.
Určete počet prvků pole a, které leží v uzavřeném intervalu ‹d,h›.
Navrhněte postup, jak správně vyřešit úlohu s co nejlepší časovou a prostorovou složitostí (měřeno nejhorším případem) vzhledem k délce vstupní posloupnosti.
(a) Popište algoritmus (včetně datových struktur, které případně budete používat). Programový kód není povinný, slovní vysvětlení zvoleného postupu řešení naopak povinné je. Nepoužívejte prosím žádné netriviální datové struktury (jako jsou např. datové typy dictionary či set v jazyce Python), jejichž algoritmus sami nepopíšete a neodvodíte jeho časovou složitost.
(b) Zdůvodněte správnost algoritmu.
(c) Odvoďte časovou a prostorovou složitost (v nejhorším případě).
Příklad:
vstup: [-22, -8, -5, 0, 1, 2, 7, 20, 20, 100, 2000, 100000]
-10 0
výstup: 3
Poznámka: Za triviální řešení v čase O(n) bude udělen jen nízký počet bodů !
(10 bodů) Je zadán binární strom o n vrcholech, v nichž jsou uložena celá čísla (mohou být i záporná). Navrhněte efektivní algoritmus, který určí
maximální součet čísel na cestě z kořenu do nějakého vrcholu
a délku nejkratší cesty (měřenou počtem hran), která tohoto součtu dosahuje.
(a) Svoje řešení zapište jako funkci v Pythonu, využijte definici třídy pro vrchol binárního stromu i hlavičku funkce uvedené níže a váš kód prosím opatřete komentáři,
(b) zdůvodněte správnost,
(c) odvoďte časovou složitost (v nejhorším případě).
class VrcholBinStromu:
"""třída pro reprezentaci vrcholu binárního stromu"""
def __init__(self, info = None, levy = None, pravy = None):
self.info = info # data
self.levy = levy # levé dítě
self.pravy = pravy # pravé dítě
def maxcena(koren : VrcholBinStromu):
"""
koren : kořen zadaného binárního stromu
vrátí : dvojici čísel (m,d), kde m je maximální součet čísel na cestě z kořenu do libovolného vrcholu stromu a
a d je délka této cesty (je-li jich více, tak nejkratší)
"""
Odpovězte na otázky.
(a) (5 bodů) Prvek x množiny M (prvků, které lze porovnávat) nazveme pseudomediánem, pokud se počty prvků množin {yεM| y<x} a {yεM| y>x} liší nejvýše o 3.
Rozhodněte, která z níže uvedených možností je pravdivá:
Kdyby se nám v algoritmu QuickSort podařilo v každém kroku vybrat v čase O(1) jako pivota pseudomedián, algoritmus setřídí zadané pole n po dvou různých čísel v nejhorším případě v čase
Θ(n<sup>2</sup>)
Θ(n log n)
Θ(n)
neplatí žádná z výše uvedených možností.
Svoji odpověď zdůvodněte (stačí stručné slovní odvození).
(b) (5 bodů) Strom hry dvou hráčů byl vygenerován do hloubky 3, všechny vrcholy v této hloubce byly ohodnoceny statickou ohodnocovací funkcí a hodnoty zbývajících vrcholů byly spočítány minimaxovým algoritmem. V bílých vrcholech je na tahu hráč maximum, v černých minimum. Výpočet bychom rádi zrychlili metodou alfa-beta prořezávání.
https://i.ibb.co/8z6PNbX/tree.png
Jaká bude minimaxová hodnota kořenu stromu? (odpověď netřeba zdůvodňovat)
V jakém pořadí je třeba procházet strom, abychom se alfa-beta prořezáváním vyhnuli vyhodnocení co nejvíce vrcholů? Pro popis pořadí můžete využít označení vrcholů a,b,c,... Stačí uvést pořadí vrcholů, netřeba zdůvodňovat.
Kolik vrcholů v takovém případě nemusíme navštívit?
Existuje nějaký průchod stromem, kdy alfa-beta prořezáváním nic neušetříme (tj. pro určení minimaxové hodnoty kořene musíme navštívit a ohodnotit všech 14 vrcholů)? Pokud ano, popište ho (použijte označení vrcholů), pokud ne, vysvětlete proč.